from collections import deque

from dataStructure.graph.graph import Graph, GraphNode


class DepthFirstSearch:
    """
    深度优先搜索类。
    """

    def __init__(self, graph):
        """
        初始化深度优先搜索对象。

        Args:
            graph (Graph): 要进行搜索的图对象。
        """
        self.graph = graph

    def iterative_depth_first_search(self, start):
        """
        执行迭代的方法深度优先搜索，从给定的起始节点开始。

        Args:
            start: 起始节点对象。

        Returns:
            List: 按访问顺序存储的节点列表。
        """
        visited = set()
        result = []
        stack = deque([start])

        while stack:
            node = stack.pop()
            if node not in visited:
                visited.add(node)
                result.append(node)
                neighbors = node.children
                stack.extend(neighbors)

        return result

    def recursive_depth_first_search(self, start):
        """
        执行递归深度优先搜索，从给定的起始节点开始。

        Args:
            start (GraphNode): 起始节点对象。

        Returns:
            List[GraphNode]: 按访问顺序存储的节点列表。
        """
        visited = set()
        result = []

        self._dfs_helper(start, visited, result)

        return result

    def _dfs_helper(self, node, visited, result):
        """
        深度优先搜索的辅助函数。

        Args:
            node (GraphNode): 当前节点对象。
            visited (set): 已访问过的节点集合。
            result (list): 按访问顺序存储的节点列表。
        """
        visited.add(node)
        result.append(node)

        neighbors = node.children
        for neighbor in neighbors:
            if neighbor not in visited:
                self._dfs_helper(neighbor, visited, result)

    def depth_limited_search(self, start, depth_limit):
        """
        执行深度限制搜索，从给定的起始节点开始，并使用深度限制。

        Args:
            start (GraphNode): 起始节点对象。
            depth_limit (int): 深度限制。

        Returns:
            List[GraphNode]: 按访问顺序存储的节点列表。
        """
        visited = set()
        result = []

        self._dls_helper(start, visited, result, depth_limit, 0)

        return result

    def _dls_helper(self, node, visited, result, depth_limit, current_depth):
        """
        深度限制搜索的辅助函数。

        Args:
            node (GraphNode): 当前节点对象。
            visited (set): 已访问过的节点集合。
            result (list): 按访问顺序存储的节点列表。
            depth_limit (int): 深度限制。
            current_depth (int): 当前深度。
        """
        visited.add(node)
        result.append(node)

        if current_depth < depth_limit:
            neighbors = node.children
            for neighbor in neighbors:
                if neighbor not in visited:
                    self._dls_helper(neighbor, visited, result, depth_limit, current_depth + 1)

    def iterative_deepening_search(self, start, max_depth):
        """
        执行迭代加深搜索，从给定的起始节点开始，并使用最大深度限制。

        Args:
            start (GraphNode): 起始节点对象。
            max_depth (int): 最大深度限制。

        Returns:
            List[GraphNode]: 按访问顺序存储的节点列表。
        """
        result = []

        for depth_limit in range(max_depth + 1):
            visited = set()
            self._dls_helper(start, visited, result, depth_limit, 0)

        return result

    def bidirectional_search(self, start, goal):
        """
        执行双向搜索，从给定的起始节点和目标节点开始。

        Args:
            start (GraphNode): 起始节点对象。
            goal (GraphNode): 目标节点对象。

        Returns:
            List[GraphNode]: 按访问顺序存储的节点列表，表示从起始节点到目标节点的路径。
        """
        if start == goal:
            return [start]

        start_visited = set()
        goal_visited = set()
        start_queue = deque([(start, [])])
        goal_queue = deque([(goal, [])])
        common_node = None

        while start_queue and goal_queue:
            current_start, start_path = start_queue.popleft()
            current_goal, goal_path = goal_queue.popleft()

            start_path.append(current_start)
            goal_path.append(current_goal)

            if current_start in goal_visited:
                common_node = current_start
                break

            if current_goal in start_visited:
                common_node = current_goal
                break

            start_visited.add(current_start)
            goal_visited.add(current_goal)

            start_neighbors = current_start.children
            for neighbor in start_neighbors:
                if neighbor not in start_visited:
                    start_queue.append((neighbor, start_path[:]))

            goal_neighbors = current_goal.children
            for neighbor in goal_neighbors:
                if neighbor not in goal_visited:
                    goal_queue.append((neighbor, goal_path[:]))

        if common_node is not None:
            start_path = start_path[::-1]
            common_index = start_path.index(common_node)
            goal_path = goal_path[1:]
            path = start_path[:common_index] + goal_path
            return path

        return []


if __name__ == "__main__":
    # Create a new graph
    graph = Graph()

    # Add nodes to the graph
    graph.add_node("A")
    graph.add_node("B")
    graph.add_node("C")
    graph.add_node("D")
    graph.add_node("E")
    graph.add_node("F")

    # Add edges between nodes
    graph.add_edge(graph.get_nodes()[0], graph.get_nodes()[1])
    graph.add_edge(graph.get_nodes()[0], graph.get_nodes()[2])
    graph.add_edge(graph.get_nodes()[0], graph.get_nodes()[3])
    graph.add_edge(graph.get_nodes()[1], graph.get_nodes()[4])
    graph.add_edge(graph.get_nodes()[1], graph.get_nodes()[5])
    
    print(graph)

    # 创建 DepthFirstSearch 对象
    dfs = DepthFirstSearch(graph)

    # 执行迭代的方法深度优先搜索
    start_node = graph.nodes[0]
    iterative_dfs_result = dfs.iterative_depth_first_search(start_node)
    print(f"从节点 {start_node.data} 开始的迭代的方法深度优先搜索结果:")
    for node in iterative_dfs_result:
        print(node.data)
    print()

    # 执行递归的方法深度优先搜索
    recursive_dfs_result = dfs.recursive_depth_first_search(start_node)
    print(f"从节点 {start_node.data} 开始的递归的方法深度优先搜索结果:")
    for node in recursive_dfs_result:
        print(node.data)
    print()
    # Output:
    # 从节点 A 开始递归的方法深度优先搜索结果:
    # A
    # B
    # E
    # F
    # C
    # D

    # 执行深度限制搜索
    depth_limit = 2
    dls_result = dfs.depth_limited_search(start_node, depth_limit)
    print(f"从节点 {start_node.data} 开始的深度限制搜索结果（深度限制为 {depth_limit}）:")
    for node in dls_result:
        print(node.data)
    print()
    # Output:
    # 从节点 A 开始的深度限制搜索结果（深度限制为 2）:
    # A
    # B
    # E

    # 执行迭代加深搜索
    max_depth = 2
    ids_result = dfs.iterative_deepening_search(start_node, max_depth)
    print(f"从节点 {start_node.data} 开始的迭代加深搜索结果（最大深度为 {max_depth}）:")
    for node in ids_result:
        print(node.data)
    print()
    # Output:
    # 从节点 A 开始的迭代加深搜索结果（最大深度为 3）:
    # A
    # B
    # E
    # F
    # C
    # D

    # 执行双向搜索
    goal_node = graph.nodes[3]
    bidirectional_result = dfs.bidirectional_search(start_node, goal_node)
    print(f"从节点 {start_node.data} 到节点 {goal_node.data} 的双向搜索结果:")
    for node in bidirectional_result:
        print(node.data)
    print()
    # Output:
    # 从节点 A 到节点 C 的双向搜索结果:
    # A
    # C
